package model.tree;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

import javax.vecmath.Point3d;
import javax.vecmath.Tuple3d;

import model.AABB;
import model.Scene;
import model.AABBConstants.Faces;
import model.AABBConstants.Slope;
import model.primitive.GenericMesh;
import model.primitive.IntersectionData;
import model.primitive.Plane;
import model.primitive.Primitive;
import model.ray.Ray;

public class OctTreeImpl implements OctTree {

	final static int MAX_ITEMS_DEFAULT = 600;
	final static double EDGE_SIZE_DEFAULT = 256;
	
	private int maxItemsByNode;
	private OctTreeNode root;

	/**
	 * CONSTRUCTORS
	 */
	// Crea un OctTreeImpl. Por default va a crear un nodo centrado en el origen
	// y de ancho de arista maximo.
	public OctTreeImpl() {
		this(MAX_ITEMS_DEFAULT);
	}

	public OctTreeImpl(int maxItems) {
		this(null, maxItems);
	}

	public OctTreeImpl( Scene scene ) {
		this(scene, MAX_ITEMS_DEFAULT);
	}
	
	public OctTreeImpl( Scene scene, int maxItems ) {
		List<AABB> boundigVolumes = new ArrayList<AABB>();
		this.maxItemsByNode = maxItems;
		
		if( scene != null )	{
			for( Primitive primitive : scene.getPrimitives() )	{
				if( primitive instanceof GenericMesh )	{
					boundigVolumes.addAll( AABB.getGenericMeshAABB( (GenericMesh)primitive ) );
//					boundigVolumes.add(new AABB(primitive));
				} else {
					boundigVolumes.add(new AABB(primitive));
				}
			}
			this.root = new OctTreeNode(new Point3d(0, 0, 0), getEdgeSize(boundigVolumes, scene));
			for( AABB aabb : boundigVolumes ) {
				this.put(aabb);
			}
		} else {
			this.root = new OctTreeNode(new Point3d(0, 0, 0), EDGE_SIZE_DEFAULT);
		}
	}
	
	private double getEdgeSize(List<AABB> boundigVolumes, Scene scene) {
		double edgeSize = 0;
		for( AABB aabb : boundigVolumes )	{
			double max = getMaxMagnitude(aabb);
			if( max > edgeSize )
				edgeSize = max;
		}
		return edgeSize == 0 ? EDGE_SIZE_DEFAULT : edgeSize*2;
	}

	private double getMaxMagnitude(AABB aabb) {
		double maxMagnitude = 0;
		Point3d point = aabb.getDmax();
		if(point != null){
			maxMagnitude = getMax(point);
		}
		point = aabb.getDmin();
		if(point != null){
			double maxMagnitude2 = getMax(point);
			if(maxMagnitude2>maxMagnitude)
				maxMagnitude = maxMagnitude2;
		}
		return maxMagnitude;
	}

	
	private double getMax(Tuple3d point) {
		double maxMagnitude = 0;
		if( Math.abs(point.x) > maxMagnitude )
			maxMagnitude = Math.abs(point.x);
		if( Math.abs(point.y) > maxMagnitude )
			maxMagnitude = Math.abs(point.y);
		if( Math.abs(point.z) > maxMagnitude )
			maxMagnitude = Math.abs(point.z);
		return maxMagnitude;
	}

	/**
	 * GET
	 */
	// Get an object closest to point.
	public AABB get(Point3d point) {
		return null;
	}

	// Get an object closest to point, within a maximum distance.
	public AABB get(Point3d point, double withinDistance) {
		return null;
	}

	/**
	 * PUT
	 * Arranco desde la raiz
	 */
	public void put(AABB obj) {
		put(root, obj);
		
	}

	/*
	 * En el metodo privado va la recursion Voy buscando
	 */
	private void put(OctTreeNode octTreeNode, AABB obj) {
		if( !octTreeNode.items.contains(obj) )
			octTreeNode.items.add(obj);
		// Estoy en una hoja
		if (octTreeNode.children == null) {
			//octTreeNode.items.add(obj);
				// No hay mas lugar, debo subdividir!
			if (octTreeNode.items.size() > this.maxItemsByNode) { 
//				System.out.println("Subdividiendo OctTree");
				if (octTreeNode.edgeSize > 0.01) {
					createChildren(octTreeNode);
					//Reasigno los hijos
					for (AABB item : octTreeNode.items) {
						put(octTreeNode, item);
					}
				} else {
					System.out.println("Se ha superado la cantidad maxima de subdivisiones tolerables.");
				}
			}
		}
		// NO estoy en una hoja, debo refinar la busqueda
		else {
			// Me fijo segun las propiedades de AABB la posicion en la que debe
			// ir.
			//
			if (belongsFNE(obj, octTreeNode)) {
				put(octTreeNode.children[0], obj);
			}
			if (belongsFSE(obj, octTreeNode)) {
				put(octTreeNode.children[1], obj);
			}
			if (belongsFSW(obj, octTreeNode)) {
				put(octTreeNode.children[2], obj);
			}
			if (belongsFNW(obj, octTreeNode)) {
				put(octTreeNode.children[3], obj);
			}
			if (belongsBNE(obj, octTreeNode)) {
				put(octTreeNode.children[4], obj);
			}
			if (belongsBSE(obj, octTreeNode)) {
				put(octTreeNode.children[5], obj);
			}
			if (belongsBSW(obj, octTreeNode)) {
				put(octTreeNode.children[6], obj);
			}
			if (belongsBNW(obj, octTreeNode)) {
				put(octTreeNode.children[7], obj);
			}
		}
	}
		
	/**
	 * REMOVE
	 */
	// Remove a object out of the tree at a location.
	public boolean remove(AABB obj) {
		return false;
	}

	/*
	 * Private classes and methods
	 */

	/*
	 * El orden de creacion(importante para los indices) es: NE, SE, SW, NW de
	 * los octantes de adelante, y luego NE, SE, SW, NW de los octantes de
	 * atras.
	 */

	private void createChildren(OctTreeNode octTreeNode) {
		octTreeNode.children = new OctTreeNode[8]; // Todos los hijos arrancan
													// en null
		octTreeNode.children[0] = new OctTreeNode(new Point3d(
				octTreeNode.center.x + octTreeNode.edgeSize / 4,
				octTreeNode.center.y + octTreeNode.edgeSize / 4,
				octTreeNode.center.z + octTreeNode.edgeSize / 4),
				octTreeNode.edgeSize / 2);
		octTreeNode.children[1] = new OctTreeNode(new Point3d(
				octTreeNode.center.x + octTreeNode.edgeSize / 4,
				octTreeNode.center.y - octTreeNode.edgeSize / 4,
				octTreeNode.center.z + octTreeNode.edgeSize / 4),
				octTreeNode.edgeSize / 2);
		octTreeNode.children[2] = new OctTreeNode(new Point3d(
				octTreeNode.center.x - octTreeNode.edgeSize / 4,
				octTreeNode.center.y - octTreeNode.edgeSize / 4,
				octTreeNode.center.z + octTreeNode.edgeSize / 4),
				octTreeNode.edgeSize / 2);
		octTreeNode.children[3] = new OctTreeNode(new Point3d(
				octTreeNode.center.x - octTreeNode.edgeSize / 4,
				octTreeNode.center.y + octTreeNode.edgeSize / 4,
				octTreeNode.center.z + octTreeNode.edgeSize / 4),
				octTreeNode.edgeSize / 2);
		octTreeNode.children[4] = new OctTreeNode(new Point3d(
				octTreeNode.center.x + octTreeNode.edgeSize / 4,
				octTreeNode.center.y + octTreeNode.edgeSize / 4,
				octTreeNode.center.z - octTreeNode.edgeSize / 4),
				octTreeNode.edgeSize / 2);
		octTreeNode.children[5] = new OctTreeNode(new Point3d(
				octTreeNode.center.x + octTreeNode.edgeSize / 4,
				octTreeNode.center.y - octTreeNode.edgeSize / 4,
				octTreeNode.center.z - octTreeNode.edgeSize / 4),
				octTreeNode.edgeSize / 2);
		octTreeNode.children[6] = new OctTreeNode(new Point3d(
				octTreeNode.center.x - octTreeNode.edgeSize / 4,
				octTreeNode.center.y - octTreeNode.edgeSize / 4,
				octTreeNode.center.z - octTreeNode.edgeSize / 4),
				octTreeNode.edgeSize / 2);
		octTreeNode.children[7] = new OctTreeNode(new Point3d(
				octTreeNode.center.x - octTreeNode.edgeSize / 4,
				octTreeNode.center.y + octTreeNode.edgeSize / 4,
				octTreeNode.center.z - octTreeNode.edgeSize / 4),
				octTreeNode.edgeSize / 2);
	}
	
	/**
     * Returns the OctTreeNode as a List of OctTreeNode objects. The elements of the
     * List are generated from a pre-order traversal of the tree.
     * @return a List<OctTreeNode>.
     */
    public List<OctTreeNode> toList() {
        List<OctTreeNode> list = new ArrayList<OctTreeNode>();
        walk(root, list);
        return list;
    }
     
    /**
     * Returns a String representation of the Tree. The elements are generated
     * from a pre-order traversal of the Tree.
     * @return the String representation of the Tree.
     */
    public String toString() {
        return toList().toString();
    }
     
    /**
     * Walks the Tree in pre-order style. This is a recursive method, and is
     * called from the toList() method with the root element as the first
     * argument. It appends to the second argument, which is passed by reference     * as it recurses down the tree.
     * @param element the starting element.
     * @param list the output of the walk.
     */
    private void walk(OctTreeNode element, List<OctTreeNode> list) {
        list.add(element);
        if(element.children != null)	{
	        for (OctTreeNode data : element.children) {
	            walk(data, list);
	        }
        }
    }
    
    
	/**
	 * 
	 * @author Alejo OctTreeNode
	 */
	private class OctTreeNode {
		Point3d center;
		double edgeSize;
		List<AABB> items;
		OctTreeNode[] children;

		Point3d FNE, FSE, FSW, FNW, BNE, BSE, BSW, BNW;
//		Plane UP, DOWN, LEFT, RIGHT, FRONT, REAR;
		Plane [] planes = new Plane[6];
		
		OctTreeNode(Point3d center, double edgeSize) {
			this.center = center;
			this.edgeSize = edgeSize;
			this.items = new ArrayList<AABB>();
			children = null;
			
			FNE = new Point3d(this.center.x + this.edgeSize/2, this.center.y + this.edgeSize/2, this.center.z + this.edgeSize/2);
			FSE = new Point3d(this.center.x + this.edgeSize/2, this.center.y - this.edgeSize/2, this.center.z + this.edgeSize/2);
			FSW = new Point3d(this.center.x - this.edgeSize/2, this.center.y - this.edgeSize/2, this.center.z + this.edgeSize/2);
			FNW = new Point3d(this.center.x - this.edgeSize/2, this.center.y + this.edgeSize/2, this.center.z + this.edgeSize/2);
			BNE = new Point3d(this.center.x + this.edgeSize/2, this.center.y + this.edgeSize/2, this.center.z - this.edgeSize/2);
			BSE = new Point3d(this.center.x + this.edgeSize/2, this.center.y - this.edgeSize/2, this.center.z - this.edgeSize/2);
			BSW = new Point3d(this.center.x - this.edgeSize/2, this.center.y - this.edgeSize/2, this.center.z - this.edgeSize/2);
			BNW = new Point3d(this.center.x - this.edgeSize/2, this.center.y + this.edgeSize/2, this.center.z - this.edgeSize/2);
			
			this.planes[0] = new Plane( FNE, BNE, BNW );	//UP
			this.planes[1] = new Plane( FSE, BSE, BSW );	//DOWN
			this.planes[2] = new Plane( BSW, FNW, BNW );	//LEFT
			this.planes[3] = new Plane( BNE, BSE, FSE );	//RIGHT
			this.planes[4] = new Plane( FNE, FSW, FSE );	//FRONT
			this.planes[5] = new Plane( BNE, BNW, BSE );	//REAR
			
		}

		public String toString() {
			String out = "";
			if (this.items.size() > 0) {
				out += "\n/***\n";
				out += "Nodo centrado en: " + this.center.toString() + "\n";
				out += "Arista de longitud: " + this.edgeSize + "\n";
				for (AABB fig : this.items) {
					out += "\tFigura entre " + fig.getDmin().toString() + " y "
							+ fig.getDmax().toString() + "\n";
				}
				out += "\n***/";
			}
			return out;
		}

		
		
		
		
		
		
		
		
		
		
		
		
		
		
		private boolean intersectsWithRay_jose(Ray ray) {
	    	
			Point3d dmin = this.BSW;
			Point3d dmax = this.FNE;
	    	switch (ray.getClasification()) {
			
			case MMM:
				
				if ((ray.getOrigin().x < dmin.x) || (ray.getOrigin().y < dmin.y) || (ray.getOrigin().z < dmin.z)
					|| (ray.getSlope(Slope.JI) * dmin.x - dmax.y + ray.getPrecomputation(Faces.XY) > 0)
					|| (ray.getSlope(Slope.IJ) * dmin.y - dmax.x + ray.getPrecomputation(Faces.YX) > 0)
					|| (ray.getSlope(Slope.JK) * dmin.z - dmax.y + ray.getPrecomputation(Faces.ZY) > 0)
					|| (ray.getSlope(Slope.KJ) * dmin.y - dmax.z + ray.getPrecomputation(Faces.YZ) > 0)
					|| (ray.getSlope(Slope.KI) * dmin.x - dmax.z + ray.getPrecomputation(Faces.XZ) > 0)
					|| (ray.getSlope(Slope.IK) * dmin.z - dmax.x + ray.getPrecomputation(Faces.ZX) > 0)
					)
					return false;
				
				return true;

			case MMP:
				
				if ((ray.getOrigin().x < dmin.x) || (ray.getOrigin().y < dmin.y) || (ray.getOrigin().z > dmax.z)
					|| (ray.getSlope(Slope.JI) * dmin.x - dmax.y + ray.getPrecomputation(Faces.XY) > 0)
					|| (ray.getSlope(Slope.IJ) * dmin.y - dmax.x + ray.getPrecomputation(Faces.YX) > 0)
					|| (ray.getSlope(Slope.JK) * dmax.z - dmax.y + ray.getPrecomputation(Faces.ZY) > 0)
					|| (ray.getSlope(Slope.KJ) * dmin.y - dmin.z + ray.getPrecomputation(Faces.YZ) < 0)
					|| (ray.getSlope(Slope.KI) * dmin.x - dmin.z + ray.getPrecomputation(Faces.XZ) < 0)
					|| (ray.getSlope(Slope.IK) * dmax.z - dmax.x + ray.getPrecomputation(Faces.ZX) > 0)
					)
					return false;
				
				return true;

			case MPM:
				
				if ((ray.getOrigin().x < dmin.x) || (ray.getOrigin().y > dmax.y) || (ray.getOrigin().z < dmin.z)
					|| (ray.getSlope(Slope.JI) * dmin.x - dmin.y + ray.getPrecomputation(Faces.XY) < 0) 
					|| (ray.getSlope(Slope.IJ) * dmax.y - dmax.x + ray.getPrecomputation(Faces.YX) > 0)
					|| (ray.getSlope(Slope.JK) * dmin.z - dmin.y + ray.getPrecomputation(Faces.ZY) < 0) 
					|| (ray.getSlope(Slope.KJ) * dmax.y - dmax.z + ray.getPrecomputation(Faces.YZ) > 0)
					|| (ray.getSlope(Slope.KI) * dmin.x - dmax.z + ray.getPrecomputation(Faces.XZ) > 0)
					|| (ray.getSlope(Slope.IK) * dmin.z - dmax.x + ray.getPrecomputation(Faces.ZX) > 0)
					)
					return false;
				
				return true;

			case MPP:
			
				if ((ray.getOrigin().x < dmin.x) || (ray.getOrigin().y > dmax.y) || (ray.getOrigin().z > dmax.z)
					|| (ray.getSlope(Slope.JI) * dmin.x - dmin.y + ray.getPrecomputation(Faces.XY) < 0) 
					|| (ray.getSlope(Slope.IJ) * dmax.y - dmax.x + ray.getPrecomputation(Faces.YX) > 0)
					|| (ray.getSlope(Slope.JK) * dmax.z - dmin.y + ray.getPrecomputation(Faces.ZY) < 0)
					|| (ray.getSlope(Slope.KJ) * dmax.y - dmin.z + ray.getPrecomputation(Faces.YZ) < 0)
					|| (ray.getSlope(Slope.KI) * dmin.x - dmin.z + ray.getPrecomputation(Faces.XZ) < 0)
					|| (ray.getSlope(Slope.IK) * dmax.z - dmax.x + ray.getPrecomputation(Faces.ZX) > 0)
					)
					return false;
				
				return true;

			case PMM:

				if ((ray.getOrigin().x > dmax.x) || (ray.getOrigin().y < dmin.y) || (ray.getOrigin().z < dmin.z)
					|| (ray.getSlope(Slope.JI) * dmax.x - dmax.y + ray.getPrecomputation(Faces.XY) > 0)
					|| (ray.getSlope(Slope.IJ) * dmin.y - dmin.x + ray.getPrecomputation(Faces.YX) < 0)
					|| (ray.getSlope(Slope.JK) * dmin.z - dmax.y + ray.getPrecomputation(Faces.ZY) > 0)
					|| (ray.getSlope(Slope.KJ) * dmin.y - dmax.z + ray.getPrecomputation(Faces.YZ) > 0)
					|| (ray.getSlope(Slope.KI) * dmax.x - dmax.z + ray.getPrecomputation(Faces.XZ) > 0)
					|| (ray.getSlope(Slope.IK) * dmin.z - dmin.x + ray.getPrecomputation(Faces.ZX) < 0)
					)
					return false;

				return true;

			case PMP:

				if ((ray.getOrigin().x > dmax.x) || (ray.getOrigin().y < dmin.y) || (ray.getOrigin().z > dmax.z)
					|| (ray.getSlope(Slope.JI) * dmax.x - dmax.y + ray.getPrecomputation(Faces.XY) > 0)
					|| (ray.getSlope(Slope.IJ) * dmin.y - dmin.x + ray.getPrecomputation(Faces.YX) < 0)
					|| (ray.getSlope(Slope.JK) * dmax.z - dmax.y + ray.getPrecomputation(Faces.ZY) > 0)
					|| (ray.getSlope(Slope.KJ) * dmin.y - dmin.z + ray.getPrecomputation(Faces.YZ) < 0)
					|| (ray.getSlope(Slope.KI) * dmax.x - dmin.z + ray.getPrecomputation(Faces.XZ) < 0)
					|| (ray.getSlope(Slope.IK) * dmax.z - dmin.x + ray.getPrecomputation(Faces.ZX) < 0)
					)
					return false;

				return true;

			case PPM:

				if ((ray.getOrigin().x > dmax.x) || (ray.getOrigin().y > dmax.y) || (ray.getOrigin().z < dmin.z)
					|| (ray.getSlope(Slope.JI) * dmax.x - dmin.y + ray.getPrecomputation(Faces.XY) < 0)
					|| (ray.getSlope(Slope.IJ) * dmax.y - dmin.x + ray.getPrecomputation(Faces.YX) < 0)
					|| (ray.getSlope(Slope.JK) * dmin.z - dmin.y + ray.getPrecomputation(Faces.ZY) < 0) 
					|| (ray.getSlope(Slope.KJ) * dmax.y - dmax.z + ray.getPrecomputation(Faces.YZ) > 0)
					|| (ray.getSlope(Slope.KI) * dmax.x - dmax.z + ray.getPrecomputation(Faces.XZ) > 0)
					|| (ray.getSlope(Slope.IK) * dmin.z - dmin.x + ray.getPrecomputation(Faces.ZX) < 0)
					)
					return false;
				
				return true;

			case PPP:

				if ((ray.getOrigin().x > dmax.x) || (ray.getOrigin().y > dmax.y) || (ray.getOrigin().z > dmax.z)
					|| (ray.getSlope(Slope.JI) * dmax.x - dmin.y + ray.getPrecomputation(Faces.XY) < 0)
					|| (ray.getSlope(Slope.IJ) * dmax.y - dmin.x + ray.getPrecomputation(Faces.YX) < 0)
					|| (ray.getSlope(Slope.JK) * dmax.z - dmin.y + ray.getPrecomputation(Faces.ZY) < 0)
					|| (ray.getSlope(Slope.KJ) * dmax.y - dmin.z + ray.getPrecomputation(Faces.YZ) < 0)
					|| (ray.getSlope(Slope.KI) * dmax.x - dmin.z + ray.getPrecomputation(Faces.XZ) < 0)
					|| (ray.getSlope(Slope.IK) * dmax.z - dmin.x + ray.getPrecomputation(Faces.ZX) < 0)
					)
					return false;
				
				return true;

			case OMM:

				if((ray.getOrigin().x < dmin.x) || (ray.getOrigin().x > dmax.x)
					|| (ray.getOrigin().y < dmin.y) || (ray.getOrigin().z < dmin.z)
					|| (ray.getSlope(Slope.JK) * dmin.z - dmax.y + ray.getPrecomputation(Faces.ZY) > 0)
					|| (ray.getSlope(Slope.KJ) * dmin.y - dmax.z + ray.getPrecomputation(Faces.YZ) > 0)
					)
					return false;

				return true;

			case OMP:

				if((ray.getOrigin().x < dmin.x) || (ray.getOrigin().x > dmax.x)
					|| (ray.getOrigin().y < dmin.y) || (ray.getOrigin().z > dmax.z)
					|| (ray.getSlope(Slope.JK) * dmax.z - dmax.y + ray.getPrecomputation(Faces.ZY) > 0)
					|| (ray.getSlope(Slope.KJ) * dmin.y - dmin.z + ray.getPrecomputation(Faces.YZ) < 0)
					)
					return false;

				return true;

			case OPM:

				if((ray.getOrigin().x < dmin.x) || (ray.getOrigin().x > dmax.x)
					|| (ray.getOrigin().y > dmax.y) || (ray.getOrigin().z < dmin.z)
					|| (ray.getSlope(Slope.JK) * dmin.z - dmin.y + ray.getPrecomputation(Faces.ZY) < 0) 
					|| (ray.getSlope(Slope.KJ) * dmax.y - dmax.z + ray.getPrecomputation(Faces.YZ) > 0)
					)
					return false;

				return true;

			case OPP:

				if((ray.getOrigin().x < dmin.x) || (ray.getOrigin().x > dmax.x)
					|| (ray.getOrigin().y > dmax.y) || (ray.getOrigin().z > dmax.z)
					|| (ray.getSlope(Slope.JK) * dmax.z - dmin.y + ray.getPrecomputation(Faces.ZY) < 0)
					|| (ray.getSlope(Slope.KJ) * dmax.y - dmin.z + ray.getPrecomputation(Faces.YZ) < 0)
					)
					return false;

				return true;

			case MOM:

				if((ray.getOrigin().y < dmin.y) || (ray.getOrigin().y > dmax.y)
					|| (ray.getOrigin().x < dmin.x) || (ray.getOrigin().z < dmin.z) 
					|| (ray.getSlope(Slope.KI) * dmin.x - dmax.z + ray.getPrecomputation(Faces.XZ) > 0)
					|| (ray.getSlope(Slope.IK) * dmin.z - dmax.x + ray.getPrecomputation(Faces.ZX) > 0)
					)
					return false;

				return true;

			case MOP:

				if((ray.getOrigin().y < dmin.y) || (ray.getOrigin().y > dmax.y)
					|| (ray.getOrigin().x < dmin.x) || (ray.getOrigin().z > dmax.z) 
					|| (ray.getSlope(Slope.KI) * dmin.x - dmin.z + ray.getPrecomputation(Faces.XZ) < 0)
					|| (ray.getSlope(Slope.IK) * dmax.z - dmax.x + ray.getPrecomputation(Faces.ZX) > 0)
					)
					return false;

				return true;

			case POM:

				if((ray.getOrigin().y < dmin.y) || (ray.getOrigin().y > dmax.y)
					|| (ray.getOrigin().x > dmax.x) || (ray.getOrigin().z < dmin.z)
					|| (ray.getSlope(Slope.KI) * dmax.x - dmax.z + ray.getPrecomputation(Faces.XZ) > 0)
					|| (ray.getSlope(Slope.IK) * dmin.z - dmin.x + ray.getPrecomputation(Faces.ZX) < 0)
					)
					return false;

				return true;

			case POP:

				if((ray.getOrigin().y < dmin.y) || (ray.getOrigin().y > dmax.y)
					|| (ray.getOrigin().x > dmax.x) || (ray.getOrigin().z > dmax.z)
					|| (ray.getSlope(Slope.KI) * dmax.x - dmin.z + ray.getPrecomputation(Faces.XZ) < 0)
					|| (ray.getSlope(Slope.IK) * dmax.z - dmin.x + ray.getPrecomputation(Faces.ZX) < 0)
					)
					return false;

				return true;

			case MMO:

				if((ray.getOrigin().z < dmin.z) || (ray.getOrigin().z > dmax.z)
					|| (ray.getOrigin().x < dmin.x) || (ray.getOrigin().y < dmin.y) 
					|| (ray.getSlope(Slope.JI) * dmin.x - dmax.y + ray.getPrecomputation(Faces.XY) > 0)
					|| (ray.getSlope(Slope.IJ) * dmin.y - dmax.x + ray.getPrecomputation(Faces.YX) > 0)
					)
					return false;

				return true;

			case MPO:

				if((ray.getOrigin().z < dmin.z) || (ray.getOrigin().z > dmax.z)
					|| (ray.getOrigin().x < dmin.x) || (ray.getOrigin().y > dmax.y) 
					|| (ray.getSlope(Slope.JI) * dmin.x - dmin.y + ray.getPrecomputation(Faces.XY) < 0) 
					|| (ray.getSlope(Slope.IJ) * dmax.y - dmax.x + ray.getPrecomputation(Faces.YX) > 0)
					)
					return false;

				return true;

			case PMO:

				if((ray.getOrigin().z < dmin.z) || (ray.getOrigin().z > dmax.z)
					|| (ray.getOrigin().x > dmax.x) || (ray.getOrigin().y < dmin.y) 
					|| (ray.getSlope(Slope.JI) * dmax.x - dmax.y + ray.getPrecomputation(Faces.XY) > 0)
					|| (ray.getSlope(Slope.IJ) * dmin.y - dmin.x + ray.getPrecomputation(Faces.YX) < 0)  
					)
					return false;

				return true;

			case PPO:

				if((ray.getOrigin().z < dmin.z) || (ray.getOrigin().z > dmax.z)
					|| (ray.getOrigin().x > dmax.x) || (ray.getOrigin().y > dmax.y)
					|| (ray.getSlope(Slope.JI) * dmax.x - dmin.y + ray.getPrecomputation(Faces.XY) < 0)
					|| (ray.getSlope(Slope.IJ) * dmax.y - dmin.x + ray.getPrecomputation(Faces.YX) < 0)
					)
					return false;

				return true;

			case MOO:

				if((ray.getOrigin().x < dmin.x)
					|| (ray.getOrigin().y < dmin.y) || (ray.getOrigin().y > dmax.y)
					|| (ray.getOrigin().z < dmin.z) || (ray.getOrigin().z > dmax.z)
					)
					return false;

				return true;

			case POO:

				if((ray.getOrigin().x > dmax.x)
					|| (ray.getOrigin().y < dmin.y) || (ray.getOrigin().y > dmax.y)
					|| (ray.getOrigin().z < dmin.z) || (ray.getOrigin().z > dmax.z)
					)
					return false;

				return true;

			case OMO:

				if((ray.getOrigin().y < dmin.y)
					|| (ray.getOrigin().x < dmin.x) || (ray.getOrigin().x > dmax.x)
					|| (ray.getOrigin().z < dmin.z) || (ray.getOrigin().z > dmax.z)
					)
					return false;

			case OPO:

				if((ray.getOrigin().y > dmax.y)
					|| (ray.getOrigin().x < dmin.x) || (ray.getOrigin().x > dmax.x)
					|| (ray.getOrigin().z < dmin.z) || (ray.getOrigin().z > dmax.z)
					)
					return false;

			case OOM:

				if((ray.getOrigin().z < dmin.z)
					|| (ray.getOrigin().x < dmin.x) || (ray.getOrigin().x > dmax.x)
					|| (ray.getOrigin().y < dmin.y) || (ray.getOrigin().y > dmax.y)
					)
					return false;

			case OOP:

				if((ray.getOrigin().z > dmax.z)
					|| (ray.getOrigin().x < dmin.x) || (ray.getOrigin().x > dmax.x)
					|| (ray.getOrigin().y < dmin.y) || (ray.getOrigin().y > dmax.y)
					)
					return false;

				return true;
			}
	    		
			return false;
		}

		
		
		
		
		
		
		
		
		
		
		
		
		
		
		/**
		 * 	Me fijo si intersecta el rayo con un octante pasando las rectas
		 * 	a su forma parametrica.
		 * 
		 *  Los intervalos del parametro para cada variable independiente deben coincidir en al menos 
		 *  un punto; si no intersectan es porque el rayo no pasa por el octante
		 */
		private boolean intersectsWithRay(Ray ray) {
            double t_x0, t_y0, t_z0, t_x1, t_y1, t_z1, aux;
            //BSW es el punto minimo del octante, y FNE el maximo 
            t_x0 = (this.BSW.x - ray.origin.x)/ray.direction.x;
            t_x1 = (this.FNE.x - ray.origin.x)/ray.direction.x;
            /*
             *  
             *  
             */
            if(t_x0 > t_x1)	{		//SWApEO para tener consistencia al comparar!!
            	
                aux = t_x0;
                
                t_x0 = t_x1;
                t_x1 = aux;
            }
            t_y0 = (this.BSW.y - ray.origin.y)/ray.direction.y;
            t_y1 = (this.FNE.y - ray.origin.y)/ray.direction.y;
            if(t_y0 > t_y1)	{
                aux = t_y0;
                t_y0 = t_y1;
                t_y1 = aux;
                
            }
            t_z0 = (this.BSW.z - ray.origin.z)/ray.direction.z;
            t_z1 = (this.FNE.z - ray.origin.z)/ray.direction.z;
            if(t_z0 > t_z1)	{
            	
                    aux = t_z0;
                    t_z0 = t_z1;
                    t_z1 = aux;
            }
            if( t_x1 < t_y0 || t_y1 < t_z0 ||
            		t_x1 < t_z0 || t_y1 < t_x0 ||
           		 		t_z1 < t_x0 || t_z1 < t_y0 
           		 	 )
            	return false;
            return true;
		}
	}
	/** End of class OctTreeNode **/
	

	/**
	 * Dado un rayo, retorna las una lista con la informacion de cada interseccion, ordenados segun la distancia
	 * (Esto se puede hacer mas eficiente con neighbour finding)
	 */
	@Override
	public List<IntersectionData> getIntersections(Ray ray) {
		List<IntersectionData> hits = new ArrayList<IntersectionData>();
		getIntersections(ray, this.root, hits);					//Arranco desde el nodo en el que esta el origen del rayo.
		Collections.sort(hits);
		
		return hits;
	}
	
	private void getIntersections(Ray ray, OctTreeNode octTreeNode, List<IntersectionData> hits) {
		if( octTreeNode != null && octTreeNode.children != null )	{		//Soy padre
			for( OctTreeNode child : octTreeNode.children )	{
				if( child != null && child.intersectsWithRay_jose(ray) )	{
					getIntersections(ray, child, hits);
				}
			}
		}
		else {		//Soy hoja
			addNodeIntersections( octTreeNode, ray, hits );
		}
	}

	private void addNodeIntersections( OctTreeNode octTreeNode, Ray ray, List<IntersectionData> hits ) {
		if( octTreeNode.items != null && octTreeNode.items.size() > 0 )	{
			for( AABB containingVolume : octTreeNode.items ) {
				containingVolume.getIntersectsWithRay(ray, hits);		//Clave
			}
		}
	}

	private boolean belongsBNW(AABB obj, OctTreeNode octTreeNode) {
		Point3d dmin = obj.getDmin();
		Point3d dmax = obj.getDmax();
		if (dmin.x <= octTreeNode.center.x && dmin.y >= octTreeNode.center.y
				&& dmin.z <= octTreeNode.center.z)
			return true;
		else if (dmax.x <= octTreeNode.center.x && dmax.y >= octTreeNode.center.y
				&& dmax.z <= octTreeNode.center.z)
			return true;
		return false;
	}

	private boolean belongsBSW(AABB obj, OctTreeNode octTreeNode) {
		Point3d dmin = obj.getDmin();
		Point3d dmax = obj.getDmax();
		if (dmin.x <= octTreeNode.center.x && dmin.y <= octTreeNode.center.y
				&& dmin.z <= octTreeNode.center.z)
			return true;
		else if (dmax.x <= octTreeNode.center.x && dmax.y <= octTreeNode.center.y
				&& dmax.z <= octTreeNode.center.z)
			return true;
		return false;
	}

	private boolean belongsBSE(AABB obj, OctTreeNode octTreeNode) {
		Point3d dmin = obj.getDmin();
		Point3d dmax = obj.getDmax();
		if (dmin.x >= octTreeNode.center.x && dmin.y <= octTreeNode.center.y
				&& dmin.z <= octTreeNode.center.z)
			return true;
		else if (dmax.x >= octTreeNode.center.x && dmax.y <= octTreeNode.center.y
				&& dmax.z <= octTreeNode.center.z)
			return true;
		return false;
	}

	private boolean belongsBNE(AABB obj, OctTreeNode octTreeNode) {
		Point3d dmin = obj.getDmin();
		Point3d dmax = obj.getDmax();
		if (dmin.x >= octTreeNode.center.x && dmin.y >= octTreeNode.center.y
				&& dmin.z <= octTreeNode.center.z)
			return true;
		else if (dmax.x >= octTreeNode.center.x && dmax.y >= octTreeNode.center.y
				&& dmax.z <= octTreeNode.center.z)
			return true;
		return false;
	}

	private boolean belongsFNW(AABB obj, OctTreeNode octTreeNode) {
		Point3d dmin = obj.getDmin();
		Point3d dmax = obj.getDmax();
		if (dmin.x <= octTreeNode.center.x && dmin.y >= octTreeNode.center.y
				&& dmin.z >= octTreeNode.center.z)
			return true;
		else if (dmax.x <= octTreeNode.center.x && dmax.y >= octTreeNode.center.y
				&& dmax.z >= octTreeNode.center.z)
			return true;
		return false;
	}

	private boolean belongsFSW(AABB obj, OctTreeNode octTreeNode) {
		Point3d dmin = obj.getDmin();
		Point3d dmax = obj.getDmax();
		if (dmin.x <= octTreeNode.center.x && dmin.y <= octTreeNode.center.y
				&& dmin.z >= octTreeNode.center.z)
			return true;
		else if (dmax.x <= octTreeNode.center.x && dmax.y <= octTreeNode.center.y
				&& dmax.z >= octTreeNode.center.z)
			return true;
		return false;
	}

	private boolean belongsFSE(AABB obj, OctTreeNode octTreeNode) {
		Point3d dmin = obj.getDmin();
		Point3d dmax = obj.getDmax();
		if (dmin.x >= octTreeNode.center.x && dmin.y <= octTreeNode.center.y
				&& dmin.z >= octTreeNode.center.z)
			return true;
		else if (dmax.x >= octTreeNode.center.x && dmax.y <= octTreeNode.center.y
				&& dmax.z >= octTreeNode.center.z)
			return true;
		return false;
	}

	private boolean belongsFNE(AABB obj, OctTreeNode octTreeNode) {
		Point3d dmin = obj.getDmin();
		Point3d dmax = obj.getDmax();
		if (dmin.x >= octTreeNode.center.x && dmin.y >= octTreeNode.center.y
				&& dmin.z >= octTreeNode.center.z)
			return true;
		else if (dmax.x >= octTreeNode.center.x && dmax.y >= octTreeNode.center.y
				&& dmax.z >= octTreeNode.center.z)
			return true;
		return false;
	}


}

